Princípio das Casas dos Pombos
O Princípio das Casas dos Pombos (ou teorema de Dirichlet ou Princípio das Gavetas de Dirichlet) é a afirmação de que se n pombos forem ser postos em m casas, e n>m , então pelo menos uma casa irá conter mais de um pombo. O primeiro relato deste princípio teria sido feito pelo matemático alemão Dirichlet em 1834, com o nome de Schubfachprinzip ("princípio das gavetas"). Embora se trate de uma evidência bem elementar, o princípio é útil para resolvermos problemas que, pelo menos à primeira vista, não são imediatos. Para aplicá-lo, devemos identificar, na situação dada, quem faz o papel dos objetos e quem faz o papel das gavetas. Exemplo Quantas pessoas são necessárias para se ter certeza que haverá pelo menos duas delas fazendo aniversário no mesmo mês? Solução: Pelo Princípio das Casas dos Pombos, se houver mais pessoas do que meses, é certo que pelo menos duas pessoas terão nascido no mesmo mês (note que os meses são as "casas" e as pessoas são os "pombos"). Como existem 12 meses, segue que são necessárias 13 pessoas. Exemplo (OBM 2006 - 3ª Fase - Nível 2) Dentre os polígonos de 5 lados, o maior número possível de vértices alinhas, isto é, pertencentes a uma única reta, é três, como mostrado a seguir. Qual é a maior quantidade de vértices alinhados que um polígono de 12 lados pode ter? Solução: Conseguimos um polígono com 8 vértices em uma mesma reta. Mostraremos que não conseguimos desenhar um polígono com 9 ou mais vértices alinhados. Para facilitar a escrita, chamaremos os vértices do polígono, na ordem que eles aparecem, de V_1,V_2,\dots,V_{12} . Vamos definir G_1=\{V_1,V_2,V_3\} G_2=\{V_4,V_5,V_6\} G_3=\{V_7,V_8,V_9\} G_4=\{V_{10},V_{11},V_{12}\} . Se escolhermos 9 vértices para pertencer a uma reta, pelo menos, algum dos conjuntos G_1, G_2, G_3, G_4 terá todos os seus vértices escolhidos. Isto não pode ocorrer, pois aí, teríamos três vértices consecutivos colineares. Logo, o máximo de polígonos que devem pertencer à reta é 8 . Generalização É ideal que, para ler esta parte, você saiba a definição e um pouco sobre as propriedades da função parte inteira. Podemos pensar de duas maneiras: * Se tivermos mn+1 objetos e quisermos colocar em m gavetas, então alguma delas terá pelo menos n+1 objetos. * Se tiveremos que colocar n objetos em k gavetas, então alguma gaveta terá um número maior ou igual a \lfloor \frac{n-1}{k}\rfloor+1 de objetos. Exemplo Suponha que iremos guardar alguns objetos em algumas gavetas. Prove que se a quantidade de gavetas for menor do que a metade da quantidade de objetos, então alguma gaveta ficará com pelo menos 3 objetos. Solução: Vamos supor que existam x gavetas. Como a quantidade de gavetas é menor do que a metade da quantidade de objetos, existem mais do que 2x objetos, ou seja, pelo menos 2x+1 . Mostraremos que ao guardar 2x+1 objetos em x gavetas, então, pelo menos alguma gaveta terá pelo menos 3 objetos. De fato, pelo Princípio da Casa dos Pombos, alguma gaveta terá uma quantidade de objetos maior ou igual a \left\lfloor \frac{2x+1-1}{x}\right\rfloor+1=\left\lfloor \frac{2x}{x}\right\rfloor+1=\left\lfloor 2\right\rfloor+1=2+1=3. Exemplo (OBM 2011 - 3ª Fase - Nível 2) No interior de um quadrado de lado 16 são colocados 1000 pontos. Mostre que é possível colocar um triângulo equilátero de lado 2\sqrt{3} no plano de modo que ele cubra pelo menos 16 destes pontos. Solução: Vamos começar encontrando a quantidade de triângulos necessária para cobrir (e até podendo ultrapassar) o quadrado. Depois usaremos o Princípio da Casa dos Pombos para mostrar que pelo menos algum desses triângulos cobrirá pelo menos 16 desses pontos. Como o lado do triângulo mede 2\sqrt{3} , sua altura será \frac{2\sqrt{3}\sqrt{3}}{2}=3 . Considere o seguinte esquema. Primeiramente, descobrimos quantas dessas faixas podemos colocar horizontalmente na figura e depois calcularemos quantos triângulos existirão nesta faixa. Observe que não podemos colocar 5 faixas, pois a altura seria 3.5=15 que é menor que 16 (o lado do quadrado). Porém podemos cobrir usando 6 dessas faixas horizontalmente. E quantos triângulos devem haver nessa faixa? Note que 4 não são suficiente para cobrir o quadrado. De fato, se tivéssemos quatro triângulos teríamos o comprimento 4.2\sqrt{3}=8\sqrt{3} que é menor que 16 . Mas 5 triângulos já dão: o comprimento da faixa será 5.2\sqrt{3}=10\sqrt{3} , que é maior do que 16 . Desta forma, as faixas devem possuir 11 triângulos ( 6 deles virados para cima e 5 para baixo) conforme ilustra a figura a seguir. Esta cobertura terá 11.6=66 triângulos. Pelo Princípio da Casa dos Pombos, se distribuirmos 1000 pontos em 66 triângulos, algum dos triângulos terá pelo menos \lfloor \frac{1000-1}{6}\rfloor+1=16 pontos. Exemplo (OBM 2002 - 3ª Fase - Nível 3) Numeramos as casas de um tabuleiro quadriculado m \times n , onde m,n \geq 2 , com os inteiros 1,2,3,\cdots,mn de modo que, para todo i \leq mn-1 , as casas i e i+1 tenham um lado em comum. Prove que existe i \leq mn-3 tal que as casas i e i+3 têm um lado em comum. Solução: A estratégia aqui será transformar o problema em outro que seja mais interessante de resolver. Para isto, temos que enxergá-lo de outra forma. Observe que podemos pensar na numeração da tabela como uma preenchimento de uma malha de pontos. Como? Vamos imaginar setas unindo números consecutivos. Por exemplo, Podemos agora pensar nisto sem os números e no lugar dos quadradinhos, podemos imaginar os seus centros. Teremos assim a seguinte figura. Ou seja, preencher a tabela conforme o enunciado é equivalente a ligar todos os pontos de uma malha com uma linha única (sem "quebras" ou bifurcações). E como seria a ideia de i e i+3 terem um lado em comum no caso das malhas? Isto acontecerá se qualquer uma das figuras a seguir aparecer na nossa malha: Assim o problema que precisamos resolver é outro: o de provar que é impossível preencher a malha sem fazer aparecer uma das figuras acima. Vamos entender um pouco melhor a figura. Existem mn pontos nesta malha. Se ligarmos eles (na horizontal e vertical), teremos quantos quadradinhos menores? Vejamos um caso particular: uma malha 4 \times 3 . Existirão, neste caso, 3-1=2 quadrados em cada linha e 4-1=3 quadrados em cada coluna, totalizando 2 \cdot 3=6 quadrados. No caso mais geral, de uma malha m \times n , teremos n-1 quadrados em cada linha e m-1 quadrados em cada coluna, totalizando (m-1)(n-1) quadradinhos menores. Quando ligarmos os números de 1 a mn estaremos passando por cima dos lados destes quadradinhos. E observe que se houver um quadradinho com 3 lados pintados, teremos alguma das possibilidades da Figura 1. Observe que, para ligarmos os números de 1 a mn , precisamos de mn-1 riscos. Portanto, para terminarmos o problema, basta mostrarmos que, ao fazer mn-1 riscos, algum dos quadrados terá três lados com riscos. Para prosseguir o raciocínio, vamos contar a quantidade de lados dos quadrados com multiplicidade. Como funciona isto? Vejamos o seguinte exemplo. Observe que se um risco for feito na "borda" da malha, ele preencherá apenas 1 lado de quadrado. Já se o risco for feito no "interior" da malha, preencherá dois lados de quadrados. Observe que, na figura 2, existem 11 segmentos: 9 na borda (que são contados uma vez só, pois pertencem a um quadrado) e 2 no interior (que são contados duas vezes, pois pertencem a dois quadrados). Assim o número de lados, com multiplicidade, é 9+2 \cdot 2=13 . Baseado em um exemplo anterior, se provarmos que o número de lados (com multiplicidade) que o caminho irá passar for maior do que a metade de lados totais dos quadradinhos menores, então algum lado irá ter 3 dos seus lados riscados. Ou seja, ao mostrarmos este fato, terminaremos o problema. A estratégia aqui será minimizar a quantidade de lados dos quadrados (com multiplicidade) e provar que este valor mínimo ainda é maior do que a metade de lados totais dos quadradinhos menores. Mas antes de minimizar, vamos descobrir como contar a quantidade de lados (com multiplicidade). Isto vai depender da quantidade de lados da borda. Vamos supor que esta quantidade seja p . Como a quantidade total de riscos é mn-1 , segue que a quantidade de lados no interior da malha será mn-1-p . Desta forma, a quantidade de lados, com multiplicidade (contando uma vez se estiver na borda e duas vezes se estiver no interior), será p+2(mn-1-p)=2mn-2-p.(*) E como minimizar a quantidade de lados (com multiplicidade)? Basta maximizarmos a quantidade de lados riscados na borda. Esta quantidade é máxima quando todos os lados da borda forem riscados, com exceção de um (afinal, não podemos dar uma volta completa). Ou seja, a quantidade de riscos na borda máxima será 2(m-1)+2(n-1)-1=2m+2n-5 . Assim, o número mínimo de lados de quadrados preenchidos será o que aparece em (*) com p=2m+2n-5 , ou seja, 2mn-2-(2m+2n-5)=2mn-2m-2n+3. Desta maneira, para terminarmos, basta mostrarmos que esta quantidade é maior do que a metade to total de lados (com multiplicidade). Como existem (m-1)(n-1) quadrados e cada um tem 4 lados, segue que esta quantidade é 4(m-1)(n-1) . Precisamos, então, mostrar que 2mn-2m-2n+3>\frac{4(m-1)(n-1)}{2}. Para isto, vamos reescrever esta equação de forma que ela seja equivalente a alguma verdadeira. Observe que esta equação pode ser reescrita como 2mn-2m-2n+3>2mn-2m-2n+2 \Leftrightarrow 3>2. Como isto é sempre verdadeiro, segue sempre existirá um quadrado que terá três de seus lados riscados e assim algum existirá i tal que i e i+3 estão lado a lado na tabela. Formulação do Princípio Envolvendo Conjuntos Se o número de elementos de um conjunto finito A é maior do que o número de elementos de um outro conjunto B , então uma função de A em B não pode ser injetora. Ligações externas Texto 002: Princípios das Casas de Pombos - Clubes de Matemática da OBMEP Categoria:Matemática Categoria:Combinatória